/**
 * 给定数组A，每一次选取某个Ai获取Ai收益，
 * 并且将数组中所有等于Ai+1与Ai-1的元素全部删除
 * 反复如此操作问最大收益是多少
 * 
 * 注意到如果选取了某个Ai，则剩下所有等于Ai的元素必然是需要选取的
 * 因此可以将所有相等的Ai合并处理，选取Ai的收益就是Ai乘以Ai在A中出现的次数
 * 
 * 这就是一个值域DP，本质上与力扣198是一样的，即选中了某个元素
 * 则相邻元素不允许选中
 * 
 */
class Solution {
using vi = vector<int>;
using Iterator = vi::const_iterator;

int N;
vi A, D, X, Y;

public:
    int deleteAndEarn(vector<int>& nums) {
        A.assign(10000 + 10, 0);
        for(auto i : nums) A[i] += i;

        return f(A.begin(), A.size());
    }

    int f(Iterator begin, int n){
        if(0 == n) return 0;
        if(1 == n) return *begin;
        if(2 == n) return max(*(begin + 1), *begin);

        vector<int> X(n, 0), Y(n, 0), D(n, 0);
        X[0] = *begin;
        Y[0] = 0;
        D[0] = X[0];

        X[1] = *(begin + 1);
        Y[1] = *(begin);
        D[1] = max(X[1], Y[1]);

        ++begin; ++begin;
        for(int i=2;i<n;++i){
            X[i] = D[i - 2] + *begin++;
            Y[i] = D[i - 1];
            D[i] = max(X[i], Y[i]);     
        }
        return D[n - 1];   
    }    
};